Tracing is a specialized use of logging to record information about a program's execution. This information is typically used by programmers for debugging purposes, and additionally, depending on the type and detail of information contained in a trace log, by experienced system administrators or technical support personnel to diagnose common problems with software. Often times, tracing utilities implemented ring buffers as the data structure to store the information obtained by the trace utility. Tasks that write into the ring buffer are known as producers or writers. Tasks that read from the ring buffer are known as consumers or readers.
With respect to a trace utility using a ring buffer for collecting data, the overhead of the writer must be as low as possible. The writer should be able to store data at any time and not worry about corruption of the buffer. A reader should be allowed to read the buffer at the same time that a writer is writing and it should not interfere with the writer.
A ring buffer with the above characteristics can easily be implemented with locks that serialize the writers and readers when a writer crosses a page boundary in the ring buffer, or when a reader swaps a page. However, locks have several disadvantages. They slow down the system. One task must wait for another task to release the lock before continuing. They may cause deadlocks if not careful. They also let the reader slow down the writer, if a reader is swapping out a page and a writer is about to cross a page boundary. Furthermore, if non-maskable interrupts (NMIs) are writing, writes may need to be dropped if the NMI fails to acquire a lock, because NMIs may never wait on a lock. There is no way to prevent an NMI. A NMI may preempt any writer that has the lock, and if the NMI were to wait on that lock it would be a deadlock.
The performance of writers, rather than readers, is more important with respect to ring buffers. The readers should be able to keep up with the collection of data, but the writers usually are writing out data from another application. The performance of the writer is also more critical because it affects the performance of the application. As such, a current goal for many tracing utilities utilizing ring buffers is to remove any locking from the writer's path. By doing so, the performance of the writer will increase.
An additional consideration with ring buffers is the mode in which they are operating. A ring buffer can operate in either overwrite mode or producer/consumer mode. Producer/consumer mode means that if the producer was to fill up the ring buffer before the consumer could free up anything, then the producer stops writing any new data to the buffer. This means that the most recent events are lost. Overwrite mode means if the produce was to fill up the buffer before the consumer could free up anything, then the producer overwrites the older data. This means that the oldest events are lost.
It is quite easy, and almost immaterial, to create a lockless design for ring buffers in producer/consumer mode because the reader and the writer are never on the same page in this mode. The writer will always stop when it reaches the reader. On the other hand, the difficulties with creating a lockless design for ring buffers in overwrite mode are substantial and daunting. As such, no solutions have been presented for such a situation. Therefore, a mechanism for a lockless ring buffer operating in overwrite mode would be beneficial.